package w5_c1_mergesort;

import insertionSort.InsertionSort;
import selectionSort.ArrayGenerator;
import selectionSort.SortingHelper;

import java.util.Arrays;

public class MergeSort {
    private MergeSort() {
    }

    /**
     * 接口
     *
     * @param arr
     * @param <E>
     */
    public static <E extends Comparable<E>> void sort(E[] arr) {
        sort(arr, 0, arr.length - 1);
    }

    /**
     * 递归实现，version 1.
     *
     * @param arr
     * @param l
     * @param r
     * @param <E>
     */
    private static <E extends Comparable<E>> void sort(E[] arr, int l, int r) {
        if (l >= r)
            return;

        //int mid = (l+r)/2;
        //上面这种方法可能会整数越界，因此写成下面的方式
        int mid = l + (r - l) / 2;
        sort(arr, l, mid);
        sort(arr, mid + 1, r);
        merge(arr, l, mid, r);
    }

    /**
     * 接口2，version 2，优化版。
     *
     * @param arr
     * @param <E>
     */
    public static <E extends Comparable<E>> void sort2(E[] arr) {
        E[] temp = Arrays.copyOf(arr, arr.length);
        sort2(arr, 0, arr.length - 1, temp);
    }

    /**
     * 递归实现，version 2.
     *
     * @param arr
     * @param l
     * @param r
     * @param temp
     * @param <E>
     */
    private static <E extends Comparable<E>> void sort2(E[] arr, int l, int r, E[] temp) {
        if (r - l <= 15) {
            InsertionSort.sort(arr, l, r);//优化2：若数组足够短，则使用插入排序.这在高级语言中不一定有用。
            return;
        }
        int mid = l + (r - l) / 2;
        sort2(arr, l, mid, temp);
        sort2(arr, mid + 1, r, temp);
        if (arr[mid].compareTo(arr[mid + 1]) > 0)//优化1：若已经有序则不进行merge。对于有序数组，O(n)
            merge2(arr, l, mid, r, temp); //优化3：改进merge
    }

    /**
     * 合并两个有序区间arr[l, mid] 和 arr[mid + 1, r]
     *
     * @param arr
     * @param l
     * @param r
     * @param <E>
     */
    private static <E extends Comparable<E>> void merge(E[] arr, int l, int mid, int r) {

        E[] temp = Arrays.copyOfRange(arr, l, r + 1);//复制[l,r+1)
        int i = l, j = mid + 1;
        // 每轮循环为arr[k]赋值
        for (int k = l; k <= r; k++) {
            if (i > mid) {//左侧区间已经取完
                arr[k] = temp[j - l];
                j++;
            } else if (j > r) {
                arr[k] = temp[i - l];
                i++;

            } else if (temp[i - l].compareTo(temp[j - l]) <= 0) {
                arr[k] = temp[i - l];
                i++;
            } else {
                arr[k] = temp[j - l];
                j++;
            }
        }
    }

    /**
     * 优化版 合并两个有序区间arr[l,mid] 和 arr[mid + 1,r]。
     *
     * @param arr
     * @param l
     * @param mid
     * @param r
     * @param temp
     * @param <E>
     */
    private static <E extends Comparable<E>> void merge2(E[] arr, int l, int mid, int r, E[] temp) {

//        E[] temp = Arrays.copyOfRange(arr, l, r + 1);//复制[l,r+1) //优化3是针对这句的。这句是每次都需要new一个对象，很耗时。
        //而将上句修改为这句后，使用的创建好的temp数组，不需要每次调用merge函数都new 1个对象了，也就优化了。
        //递归树有多少节点，就调用了多少次merge。所以是n次。这么优化就相当于省去了n次的new操作。
        System.arraycopy(arr, l, temp, l, r - l + 1);
        int i = l, j = mid + 1;
        // 每轮循环为arr[k]赋值
        for (int k = l; k <= r; k++) {
            if (i > mid) {//左侧区间已经取完
                arr[k] = temp[j];
                j++;
            } else if (j > r) {
                arr[k] = temp[i];
                i++;

            } else if (temp[i].compareTo(temp[j]) <= 0) {
                arr[k] = temp[i];
                i++;
            } else {
                arr[k] = temp[j];
                j++;
            }
        }
    }

    /**
     * 自底向上的归并排序
     *
     * @param data
     * @param <E>
     */
    public static <E extends Comparable<E>> void sortBU(E[] data) {
        E[] tmp = Arrays.copyOf(data, data.length);
        int n = data.length;
        //遍历合并区间的长度
        for (int size = 1; size < n; size += size) {
            //遍历合并的两个区间的起始位置
            //合并的是：data[i,i+size-1]和data[i+size,min(i+size*2-1,n-1)]
            for (int i = 0; i + size < n; i += 2 * size)
                //若两个连续数组需要归并
                if (data[i + size - 1].compareTo(data[i + size]) > 0)
                    //需要注意右端端点的bug。
                    merge2(data, i, i + size - 1, Math.min(i + 2 * size - 1, n - 1), tmp);
        }
    }

    /**
     * 自底向上的归并排序,插入排序优化
     *
     * @param data
     * @param <E>
     */
    public static <E extends Comparable<E>> void sortBU2(E[] data) {
        E[] tmp = Arrays.copyOf(data, data.length);
        int n = data.length;
        //遍历合并区间的长度
//        for (int size = 1; size < n; size += size) {
        for (int size = 1; size < n; size += size) {

            //遍历合并的两个区间的起始位置
            //合并的是：data[i,i+size-1]和data[i+size,min(i+size*2-1,n-1)]
            for (int i = 0; i + size < n; i += 2 * size)
                if (size <= 15 / 2)//如果区间长度小于15，用插入排序。
                    InsertionSort.sort(data, i, i + 2 * size - 1);
                else {
                    //若两个连续数组需要归并
                    if (data[i + size - 1].compareTo(data[i + size]) > 0)
                        //需要注意右端端点的bug。
                        merge2(data, i, i + size - 1, Math.min(i + 2 * size - 1, n - 1), tmp);
                }
        }
    }

    public static void main(String[] args) {
        boolean improved = false;//是否测试改进后的sort函数
        if (!improved) {
            int n = 1000;
            Integer[] arr = ArrayGenerator.generateRandomArray(n, n);
            Integer[] arr2 = Arrays.copyOf(arr, arr.length);
            Integer[] arr3 = Arrays.copyOf(arr, arr.length);
            Integer[] arr4 = Arrays.copyOf(arr, arr.length);
            Integer[] arr5 = Arrays.copyOf(arr, arr.length);
            SortingHelper.sortTest("MergeSort", arr);
            SortingHelper.sortTest("SelectionSort", arr2);
            SortingHelper.sortTest("InsertionSort", arr3);
            SortingHelper.sortTest("MergeSortBU", arr4);
            SortingHelper.sortTest("MergeSortBU2", arr5);
//            MergeSort ,n = 1000, time = 0.001351 s
//            SelectionSort ,n = 1000, time = 0.005795 s
//            InsertionSort ,n = 1000, time = 0.004909 s
//            MergeSortBU ,n = 1000, time = 0.000672 s
//            MergeSortBU2 ,n = 1000, time = 0.000425 s
        }
        test2();
    }

    /**
     * 测试改进后的sort
     */
    private static void test2() {
        int n = 5000000;
        Integer[] arr = ArrayGenerator.generateRandomArray(n, n);
//        arr = ArrayGenerator.generateOrderedArray(n);
        Integer[] arr2 = Arrays.copyOf(arr, arr.length);
        SortingHelper.sortTest("MergeSort", arr);
        SortingHelper.sortTest("MergeSort2", arr2);
        //优化1：
//        MergeSort ,n = 1000000, time = 0.402589 s
//        MergeSort2 ,n = 1000000, time = 0.008172 s
        //优化2：
//        MergeSort ,n = 5000000, time = 3.479348 s
//        MergeSort2 ,n = 5000000, time = 2.945872 s
        //优化3：
//        MergeSort ,n = 5000000, time = 3.009094 s
//        MergeSort2 ,n = 5000000, time = 2.846868 s


    }

}
